class Node(object):
    def __init__(self, item):
        self.item = item  # 对应的元素
        self.left = None  # 左子节点
        self.right = None  # 右子节点

    def __str__(self):
        # print 一个Node类时会打印 __str__ 的返回值
        return str(self.item)


class Tree(object):
    def __init__(self):
        self.root = Node('root')

    # 添加子节点到树里面
    def add(self, item):
        node = Node(item)
        # 如果二叉树为空，添加的点作为根节点
        if self.root is None:
            self.root = node
        else:
            # 在列表q中，存储根节点
            q = [self.root]
            while True:
                pop_node = q.pop(0)
                # 左子树为空，则添加到左子树
                if pop_node.left is None:
                    pop_node.left = node
                    return
                # 右子树为空，则添加到右子树
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    # 左右子树都不为空，都加入列表，重复前两步，直到添加成功为止
                    q.append(pop_node.left)
                    q.append(pop_node.right)

    # 找到 item 的父节点
    def get_parent(self, item):
        # 如果要获取的节点为根节点，则返回None，根节点没有父节点
        if self.root.item == item:
            return None
        # 在temp_list中存储根节点
        temp_list = [self.root]
        while temp_list:
            pop_node = temp_list.pop(0)
            # 如果点的左/右子树为要寻找的点
            if pop_node.left and pop_node.left.item == item:
                # 返回这个点，即为寻找点的父节点
                return pop_node
            if pop_node.right and pop_node.right.item == item:
                return pop_node
            # 左右子树都不为空，都加入列表，重复前两步，直到添加成功为止
            if pop_node.left is not None:
                temp_list.append(pop_node.left)
            if pop_node.right is not None:
                temp_list.append(pop_node.right)

    # 从二叉树中删除一个子节点
    def delete(self, item):
        # 根为空，返回False
        if self.root is None:
            return False

        # 获取待删除节点的父节点
        parent = self.get_parent(item)
        if parent:
            # 确定待删除的节点是父节点的左孩子还是右孩子
            del_node = parent.left if parent.left.item == item else parent.right
            # 如果待删除节点的左子树为空时
            if del_node.left is None:
                # 如果待删除节点是父节点的左孩子
                if parent.left.item == item:
                    # 父节点的左指针指向待删除节点的右子树
                    parent.left = del_node.right
                else:
                    # 反之，父节点的右指针指向待删除节点的右子树
                    parent.right = del_node.right
                    del del_node  # 删除变量del_node
                    return True

            # 如果待删除节点的右子树为空时
            elif del_node.right is None:
                # 如果待删除节点是父节点的左孩子
                if parent.left.item == item:
                    # 父节点的左指针指向待删除节点的左子树
                    parent.left = del_node.left
                else:
                    # 反之，父节点的右指针指向待删除节点的左子树
                    parent.right = del_node.left
                    del del_node  # 删除变量del_node
                    return True

            # 如果待删除节点的左右子树均不为空
            else:
                temp_pre = del_node
                temp_next = del_node.right  # 待删除节点的右子树

                # 寻找待删除节点右子树中的最左叶子节点并完成替代
                if temp_next.left is None:
                    temp_pre.right = temp_next.right
                    temp_next.left = del_node.left
                    temp_next.right = del_node.right
                else:
                    # 让 temp_next 指向右子树的最左叶子节点
                    while temp_next.left:
                        temp_pre = temp_next
                        temp_next = temp_next.left
                    # 替代
                    temp_pre.left = temp_next.right
                    temp_next.left = del_node.left
                    temp_next.right = del_node.right
                # 如果待删除节点是父节点的左孩子
                if parent.left.item == item:
                    parent.left = temp_next
                # 如果待删除节点是父节点的右孩子
                else:
                    parent.right = temp_next
                del del_node
                return True

        else:
            return False

    # 中序遍历
    # 先处理左子树，然后处理当前节点，再处理右子树，时间复杂度O(n)
    def inorder(self, node):
        if node is None:
            return []
        result = [node.item]
        left_item = self.inorder(node.left)
        right_item = self.inorder(node.right)
        return left_item + result + right_item

    # 后序遍历
    # 先处理左右子树，然后再处理当前节点，时间复杂度O(n)
    def postorder(self, node):
        if node is None:
            return []
        result = [node.item]
        left_item = self.postorder(node.left)
        right_item = self.postorder(node.right)
        return left_item + right_item + result

    # 前序遍历
    # 先处理当前节点，再处理左右子树
    def preorder(self, node):
        if node is None:
            return []
        result = [node.item]
        left_item = self.preorder(node.left)
        right_item = self.preorder(node.right)
        return result + left_item + right_item

